package xyz.scootaloo.oj.offer;

/**
 * @author flutterdash@qq.com
 * @since 2021/3/29 14:45
 */
public class P47 {

    public int maxValue(int[][] grid) {
        int row = grid.length;
        int column  =grid[0].length;
        int[][] dp = new int[row][column];

        dp[0][0] = grid[0][0];
        for (int c = 1; c<column; c++)
            dp[0][c] = grid[0][c] + dp[0][c - 1];
        for (int r = 1; r<row; r++)
            dp[r][0] = grid[r][0] + dp[r - 1][0];

        for (int r = 1; r<row; r++) {
            for (int c = 1; c<column; c++) {
                dp[r][c] = grid[r][c] + Math.max(dp[r - 1][c], dp[r][c  -1]);
            }
        }

        return dp[row - 1][column - 1];
    }

    public static void main(String[] args) {
        int[][] input_1 = {
                {1, 3, 1},
                {1, 5, 1},
                {4, 2, 1}
        };
        System.out.println(new P47().maxValue(input_1));
    }

}
